Decision Tree 番外篇(一) - Entropy 与 IG 在DT中的意义

Author : Benjamin142857

我们都知道在决策树ID3算法中选择特征之间的根节点顺序是用计算 $IG$ ，选取 $IG$ 值最大的特征作为根节点。但可能比较多的人都不知道为何要 $IG$ 最大值， $IG$ 最大值的意义是什么，而单个特征的 $IG$ 其实就是$Entropy_{总} - Entropy_{本特征}$ ，所以本质还是探讨 $Entropu$ 的意义，本文就在此比较通俗地简述一下 $Entropy$ 和 $IG$ 在DT中的意义。

Content:

1. 单个特征的 $Entropy$
2. 单个特征的 $IG$

单个特征的 $Entropy$

熵计算公式： $H_{x} = -\sum_{i=1}^{(x的划分区域数)}\sum_{j=1}^{(y的总标签类数)}[P_i(x_j)·log_2P_i(x_j)]$

公式解释：

1. $x的划分区域数$：就是这个特征是怎么划分的，如这个特征$x$是性别，则我们的划分就是(男，女)，划分区域数就是2。如这个特征$x$是星期几，则我们的划分就是(周一，周二，…，周日)，则$x的划分区域数$就是7
2. $y的总标签类数$：就是这组样本中的所有标签一共有几类，比如我们要做的是新闻热度的分类，要分为(冷，一般，热)，这里的标签类数就是3。如要做垃圾邮件分类，分为（垃圾，非垃圾），这里就是2.
3. $P_j(x_i)$: 就是在$x$特征的 $i$ 区域下，样本点的标签是 $j$ 的概率

若对熵公式的来源不太理解，请阅读最下方的附录 “Information Theory Note”

熵是用来度量信息混乱程度的（因为熵是信息量大小期望值），所以一般来讲信息的熵是越小越好，代表信息混乱程度低，信息比较 “整齐”。

对于决策树中特征的熵值计算也是，该特征值熵越小，说明该该特征的 “单个特征分类能力” 最好。

什么意思？就是当我们排去其他特征，只看这个特征 $x_i$ 与标签 $y$ 的关系时，特征 $x_i$ 最有代表性，分出来的 $y$ 错误率最低，类别越整齐，有序，清晰。

举个栗子:chestnut:

现在有这样一组数据，分别是一个人连续9天根据两个特征，打不打球（室外）的情况：

• 如果以两个特征划分，样本点的分布如下：

  

• 若只以 特征 $x_1$ - “下不下雨” 进行划分：

  

  我们来计算一下 $x_1$ 的熵：

  ​ $H_{x1} = [(-\frac{4}{5}log\frac{4}{5}) + (-\frac{1}{5}log\frac{1}{5})] + [(-\frac{3}{4}log\frac{3}{4}) + (-\frac{1}{4}log\frac{1}{4})]$

​

     *[下雨红点      +    下雨绿点 ] + [ 不下雨绿点 +  不下雨红点  ]*

= 1.5332

• 若只以 特征 $x_2$ - “热不热” 进行划分：

  

  我们来计算一下 $x_2$ 的熵：

  $H_{x2} = [(-\frac{1}{2}log\frac{1}{2}) + (-\frac{1}{2}log\frac{1}{2})] + [(-\frac{3}{5}log\frac{3}{5}) + (-\frac{2}{5}log\frac{2}{5})]$

  ​

  ​ [热红点 + 热绿点 ] + [ 不热红点 + 不热绿点 ]

  ​ = 1.9709

$H_{x1} < H_{x2}$，$x_1$的熵更小，所以 $x_1$的特征更具代表性，更能把种类分整齐。其实从日常经验和图我们都能很直观感受到，“下不下雨” 这一特征更能决定 “去不去打球” 。决策树中选根节点的原理也类似如此。

此外，Entropy对于连续数值型特征的分箱，多离散型数值特征的剪枝也有很重要的意义，具体请看Decision Tree番外篇（二）- 连续数值的分箱 与 剪枝

单个特征的 $IG$

信息增益计算公式：

好了，如果能明白上面 “单个特征的 $Entropy$” ，接下来单个特征的 $IG$ 就容易理解多了。我们都知道选特征是选它的 $IG$ 最大值，而上文说 “单个特征分类能力最好” 的特征是熵最小。那根据 $IG$ 计算公式：

​ $IG= Entropy_{总} - Entropy_{特征} $

​

可知二者是等价的，$Entropy_总$都是一样的，所以算 $IG$ 最大，本质就是算 $Entropy_{特征}$ 最小。那就行了，讲完~~

接下来循例举个DT中信息增益的栗子:chestnut:

• 还是这个例子：

  

在保留所有特征的情况下，我们把样本点分成四块，每一块都算它的熵即可

$H_总 = [(-1log1)] + [(-\frac{1}{3}log\frac{1}{3}) + (-\frac{2}{3}log\frac{2}{3})] + [(-\frac{1}{4}log\frac{1}{4}) + (-\frac{3}{4}log\frac{3}{4})] + [(-1log1)]$

​ 左上方块 右上方块 左下方块 右下方块

​

​ $=1.7295$

$IG_{x1} = H_总 - H_{x1} = 1.7295 - 1.5332 = 0.1963$

$IG_{x2} = H_总 - H_{x2} = 1.7295 - 1.9709 = -0.2414$

选出$IG$最大的~~

附录：

Information Theory NoteInformation Theory .md)

(-)Decision Tree番外篇（二）- 连续数值的分箱 与 剪枝

赏

thanks~~~ (⊙v⊙)

支付宝

微信